public class BST {

	BinaryNode root;
		
	/**
	 * Construct the tree.
	 */
	
	public BST() {
		root = null;
	}

	/**
	 * Insert into the tree.
	 * 
	 * @param x
	 *            the item to insert.
	 * @throws Exception
	 *             if x is already present.
	 */
	public void insert(int x) throws Exception{
		root = insert(x, root);
	}

	/**
	 * Remove from the tree..
	 * 
	 * @param x
	 *            the item to remove.
	 * @throws Execption ItemNotFound
	 *             if x is not found.
	 */
	public void remove(int x) throws Exception{
		root = remove(x, root);
	}

	/**
	 * Test if the tree is logically empty.
	 * 
	 * @return true if empty, false otherwise.
	 */
	public boolean isEmpty() {
		return root == null;
	}
	/**
	 * Public function to kill tree.
	 */
	public void Empty(){
		root = null;
	}
	
	/**
	 * Internal method to insert into a subtree.
	 * 
	 * @param x
	 *            the item to insert.
	 * @param t
	 *            the node that roots the tree.
	 * @return the new root.
	 * @throws Exception
	 *             if x is already present.
	 */

	protected BinaryNode insert(int x, BinaryNode t) throws Exception{
		if (t == null)
			t = new BinaryNode(x);
		else if (t.compareTo(x) < 0)
			t.left = insert(x, t.left);
		else if (t.compareTo(x) > 0)
			t.right = insert(x, t.right);
		else
			throw new Exception("Duplicated Id exists: " + x);
		return t;
	}

	/**
	 * Internal method to remove from a subtree.
	 * 
	 * @param x
	 *            the item to remove.
	 * @param t
	 *            the node that roots the tree.
	 * @return the new root.
	 * @throws Exception: ItemNotFound
	 *             if x is not found.
	 */
	protected BinaryNode remove(int x, BinaryNode t) throws Exception{
		if (t == null)
			throw new Exception("Item Not Found: " + x);
		if (t.compareTo(x) < 0)
			t.left = remove(x, t.left);
		else if (t.compareTo(x) > 0)
			t.right = remove(x, t.right);
		else if (t.left != null && t.right != null) // Two children
		{
			t.Modifykey(findMin(t.right).getkey());
			t.right = removeMin(t.right);
		} else
			t = (t.left != null) ? t.left : t.right;
		return t;
	}

	/**
	 * Remove minimum item from the tree.
	 * 
	 * @throws ItemNotFoundException
	 *             if tree is empty.
	 
	public void removeMin() {
		root = removeMin(root);
	}*/

	/**
	 * Find the smallest item in the tree.
	 * 
	 * @return smallest item or null if empty.
	 */
	public int findMin() {
		return elementAt(findMin(root));
	}

	/**
	 * Find the largest item in the tree.
	 * 
	 * @return the largest item or null if empty.
	 */
	public int findMax() {
		return elementAt(findMax(root));
	}

	/**
	 * Find an item in the tree.
	 * 
	 * @param x
	 *            the item to search for.
	 * @return the matching item or null if not found.
	 */
	public boolean find(int x) {
		return (x == elementAt(find(x, root)));
	}

	/**
	 * Internal method to remove minimum item from a subtree.
	 * 
	 * @param t
	 *            the node that roots the tree.
	 * @return the new root.
	 * @throws Exception ItemNotFound
	 *             if x is not found.
	 */
	protected BinaryNode removeMin(BinaryNode t) throws Exception{
		if (t == null)
			throw new Exception("ItemNotFound");
		else if (t.left != null) {
			t.left = removeMin(t.left);
			return t;
		} else
			return t.right;
	}

	/**
	 * Internal method to find the smallest item in a subtree.
	 * 
	 * @param t
	 *            the node that roots the tree.
	 * @return node containing the smallest item.
	 */
	protected BinaryNode findMin(BinaryNode t) {
		if (t != null)
			while (t.left != null)
				t = t.left;

		return t;
	}

	/**
	 * Internal method to find the largest item in a subtree.
	 * 
	 * @param t
	 *            the node that roots the tree.
	 * @return node containing the largest item.
	 */
	private BinaryNode findMax(BinaryNode t) {
		if (t != null)
			while (t.right != null)
				t = t.right;

		return t;
	}

	/**
	 * Internal method to find an item in a subtree.
	 * 
	 * @param x
	 *            is item to search for.
	 * @param t
	 *            the node that roots the tree.
	 * @return node containing the matched item.
	 */
	private BinaryNode find(int x, BinaryNode t) {
		while (t != null) {
			if (t.compareTo(x) < 0)
				t = t.left;
			else if (t.compareTo(x) > 0)
				t = t.right;
			else
				return t; // Match
		}

		return null; // Not found
	}

	/**
	 * Internal method to get key field.
	 * 
	 * @param t
	 *            the node.
	 * @return the key field or null if t is null.
	 */
	private int elementAt(BinaryNode t) {
		if (t == null)
			return 0;
		else
			return t.getkey();
	}

	public int findhight() {
		return hight(root);
	}

	/**
	 * Internal method to get tree height.
	 * 
	 * @param t
	 *            the node.
	 * @return int height.
	 */
	private int hight(BinaryNode t) {
		if (t != null) {
			int h1 = hight(t.left);
			int h2 = hight(t.right);
			return Math.max(h1, h2) + 1;
		} else
			return 0;
	}
}
